from typing import List


class Solution:
    """
    二分法进行分类讨论：
    1）nums[mid] == target: return mid
    2)升序数组，所以mid与左边界进行比较:
      a. 如果nums[mid] <= nums[left],mid值处于后升序部分,比较target和mid值的大小：nums[target]小，则需要向左逼近，即right=mid-1，否则向右逼近；
      b. 乳沟nums[mid] > nums[left],则mid值处于前升序部分，比较target和mid的大小：nums[target]大，则向右逼近，即left=mid+1,否则向左逼近
    3）left与right汇合时没找到，则不存在target，返回-1
    """
    @staticmethod
    def search(nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1
